{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Letter Tile Possibilities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #backtracking #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #回溯 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numTilePossibilities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #活字印刷"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一套活字字模&nbsp;<code>tiles</code>，其中每个字模上都刻有一个字母&nbsp;<code>tiles[i]</code>。返回你可以印出的非空字母序列的数目。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题中，每个活字字模只能使用一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>\"AAB\"\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>可能的序列为 \"A\", \"B\", \"AA\", \"AB\", \"BA\", \"AAB\", \"ABA\", \"BAA\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>\"AAABBC\"\n",
    "<strong>输出：</strong>188\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>\"V\"\n",
    "<strong>输出：</strong>1</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= tiles.length &lt;= 7</code></li>\n",
    "\t<li><code>tiles</code> 由大写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [letter-tile-possibilities](https://leetcode.cn/problems/letter-tile-possibilities/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [letter-tile-possibilities](https://leetcode.cn/problems/letter-tile-possibilities/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"AAB\"', '\"AAABBC\"', '\"V\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        counts = Counter(tiles).values()\n",
    "        n, m = len(tiles), len(counts)\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0][0] = 1\n",
    "\n",
    "        for i, cnt in enumerate(counts, start=1):\n",
    "            for j in range(n+1):\n",
    "                for k in range(min(j, cnt) + 1):\n",
    "                    f[i][j] += f[i-1][j-k] * comb(j, k)\n",
    "        \n",
    "        return sum(f[m][1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def find(count,n,res):\n",
    "    if n > 0:\n",
    "        for i in count.keys():\n",
    "            if count[i]>0:\n",
    "                res[0]+=1\n",
    "                count[i]-=1\n",
    "                find(count,n-1,res)\n",
    "                count[i]+=1\n",
    "    else:\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        count = {}\n",
    "        for i in range(len(tiles)):\n",
    "            if tiles[i] not in count.keys():\n",
    "                count[tiles[i]] = 1\n",
    "            else:\n",
    "                count[tiles[i]]+=1 \n",
    "        res = [0]\n",
    "        find(count,len(tiles),res)\n",
    "        return res[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        counts = Counter(tiles).values()  # 统计每个字母的出现次数\n",
    "        n, m = len(tiles), len(counts)\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        f[0][0] = 1  # 构造空序列的方案数\n",
    "        for i, cnt in enumerate(counts, 1):  # 枚举第 i 种字母\n",
    "            for j in range(n + 1):  # 枚举序列长度 j\n",
    "                for k in range(min(j, cnt) + 1):  # 枚举第 i 种字母选了 k 个\n",
    "                    f[i][j] += f[i - 1][j - k] * comb(j, k)  # comb 也可以预处理，见其它语言\n",
    "        return sum(f[m][1:])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        # dp[i][j]代表使用前i种字母构造长度为j的子串方式有多少种\n",
    "        # 选or不选\n",
    "        # 第i种字母不选\n",
    "        # dp[i][j] = dp[i-1][j]\n",
    "        # 第i种字母选k个，k = [1, cnt[i]]\n",
    "        # dp[i][j] = dp[i-1][j-k] * (j中选k个位置有几种选法) 对所有k求和\n",
    "        counts = Counter(tiles).values()\n",
    "        n, m = len(tiles), len(counts)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = 1 \n",
    "        for i, cnt in enumerate(counts, 1): # 枚举选第i个字母\n",
    "            for j in range(n + 1): # 枚举长度为j的子串\n",
    "                for k in range(min(j, cnt) + 1): # 枚举第i个字母选几个\n",
    "                    dp[i][j] += dp[i - 1][j - k] * comb(j, k) # j个位置选k个填进第i个字母\n",
    "        \n",
    "        return sum(dp[m][1:]) # 返回选到最后一个字母，并且子串长度大于等于1的所有方案数之和\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        count = Counter(tiles)\n",
    "        tile = set(tiles)\n",
    "\n",
    "        def dfs(cnt):\n",
    "            ans = 0\n",
    "            for i, x in cnt.items():\n",
    "                if x > 0:\n",
    "                    ans += 1\n",
    "                    cnt[i] -= 1\n",
    "                    ans += dfs(cnt)\n",
    "                    cnt[i] += 1\n",
    "            return ans\n",
    "\n",
    "        return dfs(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def dfs(cnt):\n",
    "            ans=0\n",
    "            for i,x in cnt.items():\n",
    "                print(x)\n",
    "                if x>0:\n",
    "                    ans+=1\n",
    "                    cnt[i]-=1\n",
    "                    ans+=dfs(cnt)\n",
    "                    cnt[i]+=1\n",
    "            return ans\n",
    "        cnt=Counter(tiles)\n",
    "        return dfs(cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        # 1. 回溯求所有不重复的可能组合\n",
    "        n = len(tiles)\n",
    "        path = []\n",
    "        res = set()\n",
    "        def dfs(i: int):\n",
    "            if i == n:\n",
    "                res.add(''.join(sorted(path)))\n",
    "                return \n",
    "            path.append(tiles[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "\n",
    "            dfs(i + 1)\n",
    "        \n",
    "        dfs(0) \n",
    "\n",
    "        # 2. 组合数学 计算答案 \n",
    "        ans = -1\n",
    "        for s in res:\n",
    "            sn = len(s)\n",
    "            t = 1\n",
    "            for v in Counter(s).values():\n",
    "                t *= comb(sn, v)    # 从sn个选v个元素\n",
    "                sn -= v\n",
    "            ans += t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "counter_all=Counter()\n",
    "class Solution:\n",
    "    def tims_of_str(self,tiles:str)-> int:\n",
    "        counter=Counter()\n",
    "        multi=1\n",
    "        for i,letter in enumerate(tiles):\n",
    "            counter[letter]+=1\n",
    "            multi*=i+1\n",
    "        div=1\n",
    "        for i,letter in enumerate(counter):\n",
    "            for k in range(counter[letter]):\n",
    "                div*=k+1\n",
    "        return int(multi/div)\n",
    "\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        global counter_all\n",
    "        counter_all.clear()\n",
    "        tiles=list(tiles)\n",
    "        tiles.sort\n",
    "        tiles=''.join(tiles)\n",
    "        self.numTilePossibilities2(tiles)\n",
    "        print(counter_all)\n",
    "        ans=0\n",
    "        for i,letter in enumerate(counter_all):\n",
    "            ans+=counter_all[letter]\n",
    "        return ans\n",
    "\n",
    "    @cache\n",
    "    def numTilePossibilities2(self, tiles: str) -> int:\n",
    "        global counter_all\n",
    "        if(counter_all[tiles]!=0):\n",
    "            return counter_all[tiles]\n",
    "        if(len(tiles)==1):\n",
    "            counter_all[tiles]+=1\n",
    "            return 1\n",
    "        counter=Counter()\n",
    "        for i,letter in enumerate(tiles):\n",
    "            counter[letter]+=1\n",
    "        ans=self.tims_of_str(tiles)\n",
    "        for i,letter in enumerate(counter):\n",
    "            tmp=list(tiles)\n",
    "            tmp.remove(letter)\n",
    "            tmp=''.join(tmp)\n",
    "            self.numTilePossibilities2(tmp)\n",
    "        counter_all[tiles]+=ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "counter_all=Counter()\n",
    "class Solution:\n",
    "    def tims_of_str(self,tiles:str)-> int:\n",
    "        counter=Counter()\n",
    "        multi=1\n",
    "        for i,letter in enumerate(tiles):\n",
    "            counter[letter]+=1\n",
    "            multi*=i+1\n",
    "        div=1\n",
    "        for i,letter in enumerate(counter):\n",
    "            for k in range(counter[letter]):\n",
    "                div*=k+1\n",
    "        return int(multi/div)\n",
    "\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        global counter_all\n",
    "        counter_all.clear()\n",
    "        tiles=list(tiles)\n",
    "        tiles.sort\n",
    "        tiles=''.join(tiles)\n",
    "        self.numTilePossibilities2(tiles)\n",
    "        print(counter_all)\n",
    "        ans=0\n",
    "        for i,letter in enumerate(counter_all):\n",
    "            ans+=counter_all[letter]\n",
    "        return ans\n",
    "\n",
    "    @cache\n",
    "    def numTilePossibilities2(self, tiles: str) -> int:\n",
    "        global counter_all\n",
    "        if(counter_all[tiles]!=0):\n",
    "            return counter_all[tiles]\n",
    "        if(len(tiles)==1):\n",
    "            counter_all[tiles]+=1\n",
    "            return 1\n",
    "        counter=Counter()\n",
    "        for i,letter in enumerate(tiles):\n",
    "            counter[letter]+=1\n",
    "        ans=self.tims_of_str(tiles)\n",
    "        for i,letter in enumerate(counter):\n",
    "            tmp=list(tiles)\n",
    "            tmp.remove(letter)\n",
    "            tmp=''.join(tmp)\n",
    "            self.numTilePossibilities2(tmp)\n",
    "        counter_all[tiles]+=ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        lists = []\n",
    "        for i in range(1,len(tiles)+1):\n",
    "            for j in permutations(tiles,i):\n",
    "                if \"\".join(j) not in lists:\n",
    "                    lists.append(\"\".join(j))\n",
    "        return len(lists)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        self.result = []\n",
    "        if not tiles:\n",
    "            return 0\n",
    "        array = list(tiles)\n",
    "        array.sort()\n",
    "        self.dfs(array, \"\")\n",
    "        return len(self.result)\n",
    "    \n",
    "    def dfs(self, array, path):\n",
    "        if path:\n",
    "            self.result.append(path)\n",
    "        if array and len(array) == 0:\n",
    "            return\n",
    "        \n",
    "        for i in range(len(array)):\n",
    "            if i > 0 and array[i] == array[i - 1]:\n",
    "                continue\n",
    "            self.dfs(array[:i] + array[i+1:], path + array[i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        self.result = []\n",
    "        if not tiles:\n",
    "            return 0\n",
    "        array = list(tiles)\n",
    "        array.sort()\n",
    "        self.dfs(array, \"\")\n",
    "        return len(self.result)\n",
    "    \n",
    "    def dfs(self, array, path):\n",
    "        if path:\n",
    "            print(path)\n",
    "            self.result.append(path)\n",
    "        if array and len(array) == 0:\n",
    "            return\n",
    "        \n",
    "        for i in range(len(array)):\n",
    "            if i > 0 and array[i] == array[i - 1]:\n",
    "                continue\n",
    "            self.dfs(array[:i] + array[i+1:], path + array[i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        usecheck = [False]*len(tiles)\n",
    "        self.res = []\n",
    "        tiles = ''.join(sorted(tiles))\n",
    "        self.dfs(tiles, 0, usecheck, '')\n",
    "        return len(self.res)\n",
    "\n",
    "    def dfs(self, tiles, index, usecheck, ans):\n",
    "        if index==len(tiles):\n",
    "            return    \n",
    "        for i in range(len(tiles)):\n",
    "            if usecheck[i]:\n",
    "                continue\n",
    "            if i>0 and tiles[i]==tiles[i-1] and not usecheck[i-1]:\n",
    "                continue\n",
    "            usecheck[i] = True\n",
    "            self.res.append(ans+tiles[i])\n",
    "            self.dfs(tiles, index+1, usecheck, ans+tiles[i])\n",
    "            usecheck[i] = False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        tiles = list(tiles)\n",
    "        self.ans = []\n",
    "        length = len(tiles)\n",
    "        self.mark = [False]*length\n",
    "        self.backtrack([], length, tiles)\n",
    "        print(self.ans)\n",
    "        return len(self.ans)\n",
    "\n",
    "    def backtrack(self, cache, length, tiles):\n",
    "        temp = ''.join(cache)\n",
    "        if temp not in self.ans and temp != '':\n",
    "            self.ans.append(temp)\n",
    "        if len(cache) == length:\n",
    "            return \n",
    "        for index in range(length):\n",
    "            if self.mark[index]:\n",
    "                continue\n",
    "            cache.append(tiles[index])\n",
    "            self.mark[index] = True\n",
    "            self.backtrack(cache, length, tiles)\n",
    "            cache.pop()\n",
    "            self.mark[index] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result_set = set()\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        visited = [0 for _ in range(len(tiles))]\n",
    "        self.dfs(tiles, visited, '')\n",
    "        return len(self.result_set)\n",
    "\n",
    "    def dfs(self, tiles, visited, c):\n",
    "        if len(c) == len(tiles):\n",
    "            self.result_set.add(c)\n",
    "            return\n",
    "        for i in range(len(tiles)):\n",
    "            if not visited[i]:\n",
    "                visited[i] = 1\n",
    "                self.result_set.add(c+tiles[i])\n",
    "                self.dfs(tiles, visited, c+tiles[i])\n",
    "                visited[i] = 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def dfs(tiles, path, res):\n",
    "            if path:\n",
    "                res.add(path)\n",
    "            for i in range(len(tiles)):\n",
    "                dfs(tiles[:i] + tiles[i + 1 :], path + tiles[i], res)\n",
    "\n",
    "        res = set()\n",
    "        dfs(tiles, \"\", res)\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        return sum(len(set(permutations(tiles,i))) for i in range(1,len(tiles)+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n = len(tiles)\n",
    "        res = set()\n",
    "        for i in range(1, n+1):\n",
    "            candidates = list(combinations(tiles, i))\n",
    "            for c in candidates:\n",
    "                for j in list(permutations(c)):\n",
    "                    res.add(j)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        ans = set()\n",
    "        for amount in range(1, len(tiles)+1):\n",
    "            for s in permutations(tiles, amount):\n",
    "                ans.add(s)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, nums: str) -> int:\n",
    "        result = ['']\n",
    "        n = len(nums)\n",
    "\n",
    "        for size in range(1, n+1):\n",
    "            subsets = itertools.combinations(nums, size)\n",
    "            for subset in subsets:\n",
    "                permutations = itertools.permutations(subset)\n",
    "                result.extend(list(permutations))\n",
    "\n",
    "        return len(set(result))-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        cnt = set()\n",
    "\n",
    "        def dfs(c):\n",
    "            t = set()\n",
    "            nonlocal cnt\n",
    "            for s in cnt:\n",
    "                for j in range(len(s) + 1):\n",
    "                    t.add(s[:j] + c + s[j:])\n",
    "            cnt.add(c)\n",
    "            cnt = cnt.union(t)\n",
    "\n",
    "        for c in tiles:\n",
    "            dfs(c)\n",
    "        return len(cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n = len(tiles)\n",
    "        dp = [[ tiles[i] ] for i in range(n)]\n",
    "        # allAns = [tiles[0]]\n",
    "        dp[0] = [tiles[0]]\n",
    "        for i in range(1,n):\n",
    "            for ea in dp[i-1]:\n",
    "                for idx in range(len(ea)+1):\n",
    "                    tmp = ea[:idx] + tiles[i] + ea[idx:]\n",
    "                    if ea == 'AA':\n",
    "                        print('tmp:',tmp)\n",
    "\n",
    "                    if tmp not in dp[i]:\n",
    "                        dp[i].append(tmp)\n",
    "            dp[i] += dp[i-1]\n",
    "            dp[i] = list(set( dp[i] ))\n",
    "            print(dp[i])\n",
    "        print(dp)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res += dp[i]\n",
    "        res = list(set( res ))\n",
    "        print(res)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def  dfs(n):\n",
    "            if n == m:\n",
    "                s = \"\"\n",
    "                if s.join(path.copy()) not in res:\n",
    "                    res.append(s.join(path.copy()))\n",
    "                # print(res)\n",
    "                return\n",
    "            for word in range(len(tiles)):\n",
    "                if used[word] == 0:\n",
    "                    used[word] = 1\n",
    "                    path.append(tiles[word])\n",
    "                    dfs(n+1)\n",
    "                    path.pop()\n",
    "                    used[word] = 0\n",
    "        count = 0\n",
    "        for m in range(1,len(tiles)+1):\n",
    "            res = []\n",
    "            path = []\n",
    "            used = [0]*len(tiles)\n",
    "            dfs(0)\n",
    "            print(res)\n",
    "            count = count+len(res)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        total = 0\n",
    "        for length in range(1, len(tiles) + 1):\n",
    "            permutations_set = set(permutations(tiles, length))\n",
    "            total += len(permutations_set)\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        st = {\"\"}\n",
    "        for x in tiles:\n",
    "            tmp = st.copy()\n",
    "            for y in st:\n",
    "                for i in range(0, len(y)):\n",
    "                    tmp.add(y[:i]+x+y[i:])\n",
    "                tmp.add(y+x)\n",
    "            st = tmp\n",
    "        return len(st) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        s = set()\n",
    "        for i in range(len(tiles)):\n",
    "            l = combinations(tiles, i + 1)\n",
    "            for j in l:\n",
    "                m = permutations(j)\n",
    "                tmp = set(m)\n",
    "                s = s.union(tmp)\n",
    "                # for k in m:\n",
    "                #     s.add(k)\n",
    "        return len(set(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n = len(tiles)\n",
    "        cnt = Counter()\n",
    "        for i in range(1, n + 1):\n",
    "            cnt.update(permutations(tiles, i))\n",
    "        cnt = dict(cnt)\n",
    "        return len(cnt.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n = len(tiles)\n",
    "        a = []\n",
    "        for i in range(1, n + 1):\n",
    "            a.extend(list(itertools.permutations(tiles, i)))\n",
    "        a =set([''.join(x) for x in a])\n",
    "        #print(f'a={a}')\n",
    "\n",
    "        return len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        c = Counter(tiles)\n",
    "        all = set(c.keys())\n",
    "        this = set()\n",
    "        next = set()\n",
    "        for i in all:\n",
    "            c2 = (c - Counter(i)).keys()\n",
    "            for j in c2:\n",
    "                this.add(i + j)\n",
    "        while len(this):\n",
    "            all.update(this)\n",
    "            for i in this:\n",
    "                c2 = (c - Counter(i)).keys()\n",
    "                for j in c2:\n",
    "                    next.add(i + j)\n",
    "            this = next\n",
    "            next = set()\n",
    "        return len(all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def dfs(string, d, out):\n",
    "            if d == n:\n",
    "                return\n",
    "            for i in range(len(string)):\n",
    "                if i and string[i] == string[i-1]:\n",
    "                    continue\n",
    "                res.append(out + string[i])\n",
    "                new_s = string[0:i] + string[i+1:]\n",
    "                dfs(new_s, d+1, out + string[i])\n",
    "        tiles = sorted(tiles)\n",
    "        n = len(tiles)\n",
    "        res = []\n",
    "        dfs(tiles, 0 ,'')\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        dp = set([''])\n",
    "        wait = {'': Counter(tiles)}\n",
    "        count = 0\n",
    "        for i in range(len(tiles)):\n",
    "            n_dp = set()\n",
    "            # print(dp)\n",
    "            for cur in dp:\n",
    "                for w in wait[cur]:\n",
    "                    if wait[cur][w] > 0:\n",
    "                        n_dp.add((cur+w))\n",
    "                        n_c = wait[cur].copy()\n",
    "                        n_c.subtract(w)\n",
    "                        wait[cur+w] = n_c\n",
    "                del wait[cur]\n",
    "            dp = n_dp\n",
    "            count += len(dp)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def help1(cur, other):\n",
    "            levelList = []\n",
    "            levelOtherList = []\n",
    "            for o in other:\n",
    "                newStr = cur + o\n",
    "                if newStr not in levelList:\n",
    "                    levelList.append(newStr)\n",
    "                    passMe = other[:]\n",
    "                    passMe.remove(o)\n",
    "                    levelOtherList.append(passMe[:])\n",
    "                    ansList.append(newStr)\n",
    "            for index2 in range(len(levelList)):\n",
    "                help1(levelList[index2][:],levelOtherList[index2][:])\n",
    "\n",
    "\n",
    "        tilesList = [i for i in tiles]\n",
    "        # ansList用于放所有可能的序列，即最后要返回len(ansList)\n",
    "        ansList = []\n",
    "        # 使用广度优先搜索，先找到所有要传入的cur，同时准备好对应的other\n",
    "        # 由于顺序是可以任意打乱的，所以第一个字母是谁都无所谓，唯一需要做到的是不重复\n",
    "        # 第一次用ansList来代替cur，小方法中不能从ansList里面取数据\n",
    "        otherList = []\n",
    "        for i in tiles:\n",
    "            if i not in ansList:\n",
    "                ansList.append(i)\n",
    "                passMe = tilesList[:]\n",
    "                passMe.remove(i)\n",
    "                otherList.append(passMe)\n",
    "        for index1 in range(len(ansList)):\n",
    "            help1(ansList[index1][:], otherList[index1][:])\n",
    "        return len(ansList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def help1(cur, other):\n",
    "            levelList = []\n",
    "            levelOtherList = []\n",
    "            for o in other:\n",
    "                newStr = cur + o\n",
    "                if newStr not in levelList:\n",
    "                    levelList.append(newStr)\n",
    "                    passMe = other[:]\n",
    "                    passMe.remove(o)\n",
    "                    levelOtherList.append(passMe[:])\n",
    "                    ansList.append(newStr)\n",
    "            # ansList.append(levelList)\n",
    "            for index2 in range(len(levelList)):\n",
    "                help1(levelList[index2][:],levelOtherList[index2][:])\n",
    "\n",
    "\n",
    "        tilesList = [i for i in tiles]\n",
    "        # ansList用于放所有可能的序列，即最后要返回len(ansList)\n",
    "        ansList = []\n",
    "        # 使用广度优先搜索，先找到所有要传入的cur，同时准备好对应的other\n",
    "        # 由于顺序是可以任意打乱的，所以第一个字母是谁都无所谓，唯一需要做到的是不重复\n",
    "        # 第一次用ansList来代替cur，小方法中不能从ansList里面取数据\n",
    "        otherList = []\n",
    "        for i in tiles:\n",
    "            if i not in ansList:\n",
    "                ansList.append(i)\n",
    "                passMe = tilesList[:]\n",
    "                passMe.remove(i)\n",
    "                otherList.append(passMe)\n",
    "        for index1 in range(len(ansList)):\n",
    "            help1(ansList[index1][:], otherList[index1][:])\n",
    "        # print(ansList)\n",
    "        return len(ansList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def helper(path):\n",
    "            self.ans.add(''.join(path))\n",
    "            for i in range(n):\n",
    "                if visited[i]==False:\n",
    "                    visited[i] = True\n",
    "                    path.append(tiles[i])\n",
    "                    helper(path)\n",
    "                    visited[i] = False\n",
    "                    path.pop()\n",
    "\n",
    "\n",
    "\n",
    "        n = len(tiles)\n",
    "        visited = [False] * n\n",
    "        self.ans = set()\n",
    "        helper([])\n",
    "        return len(self.ans) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def helper(path):\n",
    "            self.ans.add(''.join(path))\n",
    "            for i in range(n):\n",
    "                if visited[i]==False:\n",
    "                    visited[i] = True\n",
    "                    path.append(tiles[i])\n",
    "                    helper(path)\n",
    "                    visited[i] = False\n",
    "                    path.pop()\n",
    "\n",
    "\n",
    "\n",
    "        n = len(tiles)\n",
    "        visited = [False] * n\n",
    "        self.ans = set()\n",
    "        helper([])\n",
    "        return len(self.ans) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        v=[0]*26\n",
    "        for i in tiles:\n",
    "            v[ord(i)-ord('A')]+=1\n",
    "        idx=0\n",
    "        stack=[v]\n",
    "        while idx<len(stack):\n",
    "            for i in range(26):\n",
    "                now=stack[idx].copy()\n",
    "                if now[i]>0:\n",
    "                    now[i]-=1\n",
    "                    stack.append(now)\n",
    "            idx+=1\n",
    "        # print(stack)\n",
    "        # print(v)\n",
    "        return len(stack)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        tiles = ''.join(sorted(tiles))\n",
    "        results = []\n",
    "        path = ''\n",
    "        used = [ 0 for _ in range(len(tiles))]\n",
    "\n",
    "        def dfs(path,used):\n",
    "            if path:\n",
    "                results.append(path[:])\n",
    "\n",
    "            for  i in range(len(tiles)):\n",
    "                if used[i] == 1:\n",
    "                    continue\n",
    "                if i>0 and used[i-1] == 0 and tiles[i-1] == tiles[i]:\n",
    "                    continue\n",
    "                used[i] = 1\n",
    "                path = path + tiles[i]\n",
    "                dfs(path,used)\n",
    "                path = path[:-1]\n",
    "                used[i] = 0\n",
    "\n",
    "        dfs(path,used)\n",
    "        return len(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def backtrack(first, t, visited):\n",
    "            tt = ''.join(t[:])\n",
    "            if first <= n and tt not in ans:\n",
    "                ans.append(''.join(t[:]))\n",
    "            if first > n:\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    t.append(tiles[i])                    \n",
    "                    backtrack(first + 1, t, visited)\n",
    "                    t.pop()\n",
    "                    visited.remove(i)\n",
    "        n = len(tiles)\n",
    "        ans = []\n",
    "        visited = set()\n",
    "        backtrack(0, [], visited)\n",
    "        return len(ans) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n= len(tiles)\n",
    "        ans = []\n",
    "        path = []\n",
    "        items = sorted(tiles) \n",
    "        used = [False] * n\n",
    "\n",
    "\n",
    "        def backtrack(items: List[str],start: int):\n",
    "            ans.append(path.copy)\n",
    "            if len(path) == n:\n",
    "                return \n",
    "\n",
    "            for i in range(n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                if i>0 and items[i-1] == items[i]  and not used[i-1]:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                path.append(items[i])\n",
    "                backtrack(items, i+1)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        backtrack(items, 0)\n",
    "        return len(ans) -1 \n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        cs = list(tiles)\n",
    "        n = len(cs)\n",
    "        res = []\n",
    "        path = []\n",
    "        used = [False] * n\n",
    "        cs.sort()\n",
    "\n",
    "        def backtrack(idx):\n",
    "            if len(path):\n",
    "                res.append(''.join(path))\n",
    "\n",
    "            for i in range(n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                if i >= 1 and cs[i] == cs[i - 1] and not used[i - 1]:\n",
    "                    continue\n",
    "\n",
    "                used[i] = True\n",
    "                path.append(cs[i])\n",
    "\n",
    "                backtrack(i)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "\n",
    "        backtrack(0)\n",
    "        \n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        seqs = defaultdict(list)\n",
    "        res = 0\n",
    "        def dfs(s, depth, ts):\n",
    "            nonlocal seqs, res\n",
    "            if depth >= 1 and s not in seqs[depth]:\n",
    "                res += 1\n",
    "                seqs[depth].append(s)\n",
    "            for i in range(len(ts)):\n",
    "                dfs(s + ts[i], depth + 1, ts[:i] + ts[i + 1:])\n",
    "        dfs(\"\", 0, tiles)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        l = len(tiles)\n",
    "        def dfs(path,n,record):\n",
    "            if path and path not in ans:\n",
    "                ans.append(path[:])\n",
    "                nonlocal con\n",
    "                con += 1\n",
    "            if n == l:\n",
    "                return\n",
    "            for i in tiles:\n",
    "                if i in record:\n",
    "                    record.remove(i)\n",
    "                    dfs(path+i,n+1,record)\n",
    "                    record.append(i)\n",
    "            return\n",
    "        ans , con = [] , 0\n",
    "        dfs('',0,' '.join(tiles).split())\n",
    "        return con"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        ans = set()\n",
    "        def helper(left,right):\n",
    "            if left:\n",
    "                ans.add(left)\n",
    "            for i in range(len(right)):\n",
    "                helper(left+right[i],right[:i]+right[i+1:])\n",
    "        helper('',tiles)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        visited = [False] * len(tiles)\n",
    "        tiles = sorted(tiles)\n",
    "        record = set()\n",
    "        def dfs(path):\n",
    "            if path:\n",
    "                record.add(tuple(path))\n",
    "            # print(path)\n",
    "            \n",
    "            if len(path) == len(tiles):\n",
    "                return\n",
    "            \n",
    "            for i in range(len(tiles)):\n",
    "                if visited[i]:\n",
    "                    continue\n",
    "                \n",
    "                if i > 0 and tiles[i] == tiles[i - 1] and visited[i - 1]:\n",
    "                    continue\n",
    "                \n",
    "                visited[i] = True\n",
    "                path.append(tiles[i])\n",
    "                dfs(path)\n",
    "                path.pop()\n",
    "                visited[i] = False\n",
    "        \n",
    "        dfs([])\n",
    "        # print(record)\n",
    "        return len(record)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        hashset = set()\n",
    "        hashset.add('')\n",
    "        res = 0 \n",
    "        def backtrace(path,xuanze):\n",
    "            nonlocal res \n",
    "            nonlocal hashset\n",
    "            ps = ''.join(path)\n",
    "            if ps not in hashset:\n",
    "                hashset.add(ps)\n",
    "                res += 1\n",
    "            for index in range(len(tiles)):\n",
    "                if index not in xuanze:\n",
    "                    xuanze.add(index)\n",
    "                    path.append(tiles[index])\n",
    "                    backtrace(path,xuanze)\n",
    "                    path.pop()\n",
    "                    xuanze.remove(index)\n",
    "        backtrace([],set())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        tot = set()\n",
    "        \n",
    "        def dfs(s:str, state:int) -> bool:\n",
    "            tot.add(s)\n",
    "            for i, ch in enumerate(tiles):\n",
    "                if (state >> i) & 1 == 0:\n",
    "                    dfs(s + ch, state | (1 << i))\n",
    "\n",
    "        dfs(\"\", 0)\n",
    "        return len(tot) - 1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n=len(tiles)\n",
    "        res=[]\n",
    "        def dfs(max_len,path):\n",
    "            if len(path)==max_len:\n",
    "                res.append(path)\n",
    "                return \n",
    "            havevisted=set()\n",
    "            for i in range(n):\n",
    "                if not tiles[i] in havevisted and not visited[i]:\n",
    "                    havevisted.add(tiles[i])\n",
    "                    visited[i]=True\n",
    "                    dfs(max_len,path+tiles[j])\n",
    "                    visited[i]=False\n",
    "                \n",
    "\n",
    "        visited=[False]*n \n",
    "        for i in range(1,n+1):\n",
    "            havevisted=set()\n",
    "            for j in range(n):\n",
    "                if tiles[j] not in havevisted:\n",
    "                    havevisted.add(tiles[j])\n",
    "                    visited[j]=True\n",
    "                    dfs(i,tiles[j])\n",
    "                    visited[j]=False\n",
    "        return len(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        def dfs(path):\n",
    "            # print(path, check)\n",
    "            res.append(path)\n",
    "            for i in range(n):\n",
    "                if check[i] == 1: continue\n",
    "                if i and tiles[i] == tiles[i-1] and check[i-1] == 0:\n",
    "                    continue\n",
    "                check[i] = 1\n",
    "                dfs(path+tiles[i])\n",
    "                check[i] = 0\n",
    "        res = []\n",
    "        tiles = \"\".join(sorted(tiles))\n",
    "        n = len(tiles)\n",
    "        check = [0] * n\n",
    "        dfs(\"\")\n",
    "        return len(res) -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        ans=[]\n",
    "        n=len(tiles)\n",
    "        used=[False]*n\n",
    "        tiles=sorted( tiles)\n",
    "        def dfs(i,tmp):\n",
    "            if i==n:\n",
    "                return\n",
    "            if i!=-1:\n",
    "                ans.append(''.join(tmp))\n",
    "            k=''\n",
    "            for j in range(0,n):\n",
    "                if used[j]:\n",
    "                    continue\n",
    "                if tiles[j]==k:\n",
    "                    continue\n",
    "                tmp.append(tiles[j])\n",
    "                used[j]=True\n",
    "                dfs(j,tmp)\n",
    "                k=tmp.pop()\n",
    "                used[j]=False\n",
    "        dfs(-1,[])\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "\n",
    "        def dfs(tiles, path, visited):\n",
    "            if path and len(path) <= len(tiles):\n",
    "                res.append(path)\n",
    "                if len(path) == len(tiles):\n",
    "                    return\n",
    "            for i in range(len(tiles)):\n",
    "                if visited[i]:  continue\n",
    "                if i > 0 and tiles[i] == tiles[i-1] and not visited[i-1]:\n",
    "                    continue\n",
    "                path += tiles[i]\n",
    "                visited[i] = 1\n",
    "                dfs(tiles, path, visited)\n",
    "                path = path[:-1]\n",
    "                visited[i] = 0\n",
    "        tiles = list(tiles)\n",
    "        tiles.sort()\n",
    "        visited = [0] * len(tiles)\n",
    "        res = []\n",
    "        dfs(tiles, \"\", visited)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        rslt = []\n",
    "        def search(now, candi):\n",
    "            if not candi:\n",
    "                if now not in rslt:\n",
    "                    rslt.append(now)\n",
    "                return\n",
    "            if now not in rslt and now != '':\n",
    "                rslt.append(now)\n",
    "            for ix, i in enumerate(candi):\n",
    "                new_candi = [i for jx, i in enumerate(candi) if jx != ix]\n",
    "                search(now + i, new_candi)\n",
    "\n",
    "        search('', tiles)\n",
    "        # print(rslt)\n",
    "        return len(rslt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        res = []\n",
    "        tiles = list(tiles)\n",
    "        n = len(tiles)\n",
    "        \n",
    "        def dfs(tiles, tmpstr):\n",
    "            if tmpstr not in res:\n",
    "                res.append(tmpstr)\n",
    "            if len(tmpstr) == n:\n",
    "                return \n",
    "            for i in range(len(tiles)):\n",
    "                dfs(tiles[:i] + tiles[i+1:], tmpstr + tiles[i])\n",
    "\n",
    "        dfs(tiles, '')\n",
    "        print(res)\n",
    "        return len(res) - 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        n=len(tiles)\n",
    "        used=[0]*n\n",
    "        def dfs():\n",
    "            if 0<len(path)<=n:\n",
    "                ans.append(path[:])\n",
    "            if len(path)==n:\n",
    "                return\n",
    "            selected=set()\n",
    "            for i in range(n):\n",
    "                if tiles[i] not in selected and not used[i]:\n",
    "                    path.append(tiles[i])\n",
    "                    used[i]=1\n",
    "                    selected.add(tiles[i])\n",
    "                    dfs()\n",
    "                    path.pop()\n",
    "                    used[i]=0\n",
    "        dfs()\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        n=len(tiles)\n",
    "        used=[0]*n\n",
    "        def dfs():\n",
    "            if 0<len(path)<=n:\n",
    "                ans.append(path[:])\n",
    "            if len(path)==n:\n",
    "                return\n",
    "            selected=set()\n",
    "            for i in range(n):\n",
    "                if tiles[i] not in selected and not used[i]:\n",
    "                    path.append(tiles[i])\n",
    "                    used[i]=1\n",
    "                    selected.add(tiles[i])\n",
    "                    dfs()\n",
    "                    path.pop()\n",
    "                    used[i]=0\n",
    "        dfs()\n",
    "        return len(ans)\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        tiles=sorted(list(tiles))\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        n=len(tiles)\n",
    "        used=[0]*n\n",
    "        def dfs():\n",
    "            if 0<len(path)<=n:\n",
    "                ans.append(path[:])\n",
    "            if len(path)==n:\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if i>0 and tiles[i]==tiles[i-1] and used[i-1]==0:\n",
    "                    continue\n",
    "                if not used[i]:\n",
    "                    path.append(tiles[i])\n",
    "                    used[i]=1\n",
    "                    dfs()\n",
    "                    path.pop()\n",
    "                    used[i]=0\n",
    "        dfs()\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(tiles)\n",
    "        tiles = sorted(tiles)\n",
    "        used = [False for _ in range(n)]\n",
    "        def backtrack():\n",
    "            nonlocal res\n",
    "            res.append(path.copy())\n",
    "            for i in range(n):\n",
    "                if used[i] or (i > 0 and tiles[i] == tiles[i-1] and not used[i-1]):\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                path.append(tiles[i])\n",
    "                backtrack()\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        backtrack()\n",
    "        return len(res) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        ans = []  # 用于保存所有排列结果\n",
    "        path = []  # 当前排列的路径\n",
    "        n = len(tiles)\n",
    "        visited = [False] * n  # 记录字符是否被使用过\n",
    "        tiles = sorted(tiles)  # 排序，以便处理字符重复情况\n",
    "\n",
    "        def backtrack():\n",
    "            nonlocal ans\n",
    "            ans.append(path.copy())  # 将当前排列添加到结果中\n",
    "            for i in range(n):\n",
    "                if visited[i] or (i > 0 and tiles[i] == tiles[i - 1] and not visited[i - 1]):\n",
    "                    continue\n",
    "                visited[i] = True\n",
    "                path.append(tiles[i])\n",
    "                backtrack()\n",
    "                path.pop()\n",
    "                visited[i] = False\n",
    "\n",
    "        backtrack()\n",
    "        return len(ans) - 1  # 减去初始空排列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        row = []\n",
    "        rows = []\n",
    "        data = sorted(tiles)\n",
    "        def inner(idx, data):\n",
    "            for i in range(idx, len(data)):\n",
    "                if i > 0 and data[i-1] == data[i]:\n",
    "                    continue\n",
    "                n = data.copy()\n",
    "                row.append(n.pop(i))\n",
    "                rows.append(row.copy())\n",
    "                inner(0, n)\n",
    "                row.pop()\n",
    "        inner(0, data)\n",
    "        return len(rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        row = []\n",
    "        rows = []\n",
    "        data = sorted(tiles)\n",
    "        print(tiles)\n",
    "        def inner(idx, data):\n",
    "            for i in range(idx, len(data)):\n",
    "                if i > 0 and data[i-1] == data[i]:\n",
    "                    continue\n",
    "                n = data.copy()\n",
    "                row.append(n.pop(i))\n",
    "                rows.append(row.copy())\n",
    "                inner(0, n)\n",
    "                row.pop()\n",
    "        inner(0, data)\n",
    "        return len(rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        res = []\n",
    "        track = []\n",
    "        n = len(tiles)\n",
    "        used = [False] * n\n",
    "        nums = list(tiles)\n",
    "        nums.sort()\n",
    "        def backtracking(nums):\n",
    "            if track:\n",
    "                res.append(track[::])\n",
    "            for i in range(len(nums)):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:\n",
    "                    continue\n",
    "                track.append(nums[i])\n",
    "                used[i] = True\n",
    "                backtracking(nums)\n",
    "                track.pop()\n",
    "                used[i] = False\n",
    "        backtracking(nums)\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "      visited = set()\n",
    "      temp = []\n",
    "      def dfs(string):\n",
    "        if not string:\n",
    "          return\n",
    "        for i in range(len(string)):\n",
    "          temp.append(string[i])\n",
    "          cur = \"\".join(temp)\n",
    "          if cur not in visited:\n",
    "            visited.add(cur)\n",
    "            dfs(string[:i] + string[i+1:])\n",
    "          temp.pop()\n",
    "      dfs(tiles)\n",
    "      return len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "      visited = set()\n",
    "      temp = []\n",
    "      def dfs(string):\n",
    "        if not string:\n",
    "          return\n",
    "        for i in range(len(string)):\n",
    "          temp.append(string[i])\n",
    "          cur = \"\".join(temp)\n",
    "          if cur not in visited:\n",
    "            visited.add(cur)\n",
    "            dfs(string[:i] + string[i+1:])\n",
    "          temp.pop()\n",
    "      dfs(tiles)\n",
    "      return len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n=len(tiles)\n",
    "        s=set()\n",
    "        def dfs(bit,before,length):\n",
    "            if length==n:\n",
    "                s.add(before)\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if bit>>i&1==0:\n",
    "                    before+=tiles[i]\n",
    "                    s.add(before)\n",
    "                    dfs(bit|(1<<i),before,length+1)\n",
    "                    before=before[:-1]\n",
    "\n",
    "        dfs(0,'',0)\n",
    "        # print(s)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n=len(tiles)\n",
    "        s=set()\n",
    "        def dfs(bit,before,length):\n",
    "            if length==n:\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if bit>>i&1==0:\n",
    "                    before+=tiles[i]\n",
    "                    s.add(before)\n",
    "                    dfs(bit|(1<<i),before,length+1)\n",
    "                    before=before[:-1]\n",
    "\n",
    "        dfs(0,'',0)\n",
    "        # print(s)\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n = len(tiles)\n",
    "        s = set()\n",
    "\n",
    "        def perm(arr, path):\n",
    "            if len(path) == len(arr):\n",
    "                s.add(''.join(arr[_] for _ in path))\n",
    "                return\n",
    "            for i in range(len(arr)):\n",
    "                if i in path:\n",
    "                    continue\n",
    "                perm(arr, path + [i])\n",
    "        \n",
    "        for i in range(1, 1 << n):\n",
    "            t = '{:b}'.format(i)\n",
    "            t = '0' * (n - len(t)) + t\n",
    "            arr = []\n",
    "            for j, c in enumerate(t):\n",
    "                if int(c):\n",
    "                    arr.append(tiles[j])\n",
    "            perm(arr, [])\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n=len(tiles)\n",
    "        vis=set()\n",
    "        hash=[False]*n \n",
    "        cnt=0\n",
    "        s=[]\n",
    "        def dfs(s):\n",
    "            nonlocal cnt\n",
    "            if len(s) and tuple(s) not in vis:\n",
    "                vis.add(tuple(s))\n",
    "                cnt+=1\n",
    "            for i in range(n):\n",
    "                if not hash[i]:\n",
    "                    hash[i]=True\n",
    "                    s.append(tiles[i])\n",
    "                    dfs(s)\n",
    "                    s.pop()\n",
    "                    hash[i]=False\n",
    "        dfs(s)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n=len(tiles)\n",
    "        vis=set()\n",
    "        hash=[False]*n \n",
    "        cnt=0\n",
    "        s=[]\n",
    "        def dfs(u:int,s):\n",
    "            nonlocal cnt\n",
    "            if u>n:\n",
    "                return None\n",
    "            if len(s) and tuple(s) not in vis:\n",
    "                vis.add(tuple(s))\n",
    "                cnt+=1\n",
    "            for i in range(n):\n",
    "                if not hash[i]:\n",
    "                    hash[i]=True\n",
    "                    s.append(tiles[i])\n",
    "                    dfs(u+1,s)\n",
    "                    s.pop()\n",
    "                    hash[i]=False\n",
    "        dfs(0,s)\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        st=set()\n",
    "        n=len(tiles)\n",
    "        def backup(v:set,l:List):\n",
    "            if len(v)==n:\n",
    "                st.add(tuple(l))\n",
    "                return\n",
    "            for i,x in enumerate(tiles):\n",
    "                if i not in v:\n",
    "                    v.add(i)\n",
    "                    backup(v,l)\n",
    "                    l.append(x)\n",
    "                    backup(v,l)\n",
    "                    l.pop()\n",
    "                    v.remove(i)\n",
    "        backup(set(),[])\n",
    "        print(st)\n",
    "        return len(st)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        tempdic = {}\n",
    "        vis = [False for i in range(len(tiles))]\n",
    "        tot = 0\n",
    "        def dfs(pos,now_str):\n",
    "            nonlocal tot\n",
    "            for i,ch in enumerate(tiles):\n",
    "                if vis[i] == False and now_str + ch not in tempdic:\n",
    "                    tempdic[now_str + ch] = 0\n",
    "                    tot = tot + 1\n",
    "                    vis[i] = True\n",
    "                    dfs(i,now_str+ch)\n",
    "                    vis[i] = False\n",
    "        for p,ch in enumerate(tiles):\n",
    "            if vis[p] == False and ch not in tempdic:\n",
    "                    tempdic[ch] = 0\n",
    "                    tot = tot + 1\n",
    "                    vis[p] = True\n",
    "                    dfs(p,ch)\n",
    "                    vis[p] = False   \n",
    "        # print(tempdic)\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        n = len(tiles)\n",
    "        vis = [False] * n\n",
    "\n",
    "        arr = set()\n",
    "\n",
    "        def dfs(x, word):\n",
    "            if x == 0:\n",
    "                arr.add(word)\n",
    "            for i, c in enumerate(tiles):\n",
    "                if not vis[i]:\n",
    "                    vis[i] = True\n",
    "                    dfs(x - 1, word + c)\n",
    "                    vis[i] = False\n",
    "\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            dfs(i, '')\n",
    "        \n",
    "        return len(arr)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        result = set()\n",
    "\n",
    "        visited = []\n",
    "        def dfs(string, index):\n",
    "            result.add(string)\n",
    "            for i in range(len(tiles)):\n",
    "                if i in visited:\n",
    "                    continue\n",
    "                visited.append(i)\n",
    "                dfs(string + tiles[i], i)\n",
    "                visited.pop(-1)\n",
    "\n",
    "        for i in range(len(tiles)):\n",
    "            visited.append(i)\n",
    "            dfs(tiles[i], i)\n",
    "            visited.pop(-1)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        temp={}\n",
    "        ans=set()\n",
    "        for i in tiles:\n",
    "            temp[i]=temp.get(i,0)+1\n",
    "        def dps(x):\n",
    "            if len(x)==len(tiles):\n",
    "                return\n",
    "            for i,j in temp.items():\n",
    "                if j<=0:\n",
    "                    continue\n",
    "                y=x+i\n",
    "                ans.add(y)\n",
    "                temp[i]-=1\n",
    "                dps(y)\n",
    "                temp[i]+=1\n",
    "        dps('')\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        str_set = set()\n",
    "        def dfs(step:int, s: str, state: int):\n",
    "            if step == len(tiles):\n",
    "                str_set.add(s)\n",
    "                return\n",
    "            #1.不选\n",
    "            dfs(step + 1,s,state)\n",
    "            #2.选哪个\n",
    "            i = len(tiles) - 1\n",
    "            while i >= 0:\n",
    "                if ((state >> i) & 1) == 0:\n",
    "                    dfs(step + 1, s+tiles[i:i+1], state | (1 <<i))\n",
    "                i-=1 \n",
    "        dfs(0,\"\",0)\n",
    "        str_set.remove(\"\")\n",
    "        return len(str_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        chongfu = set()\n",
    "        my_len = len(tiles)\n",
    "        used = set()\n",
    "        def dfs(i,tiles,str):\n",
    "            used.add(i)\n",
    "            str = str+tiles[i]\n",
    "            chongfu.add(str)\n",
    "            for num in range(0,my_len):\n",
    "                if num in used:\n",
    "                    continue\n",
    "                dfs(num,tiles,str)\n",
    "            str = str[:-1]\n",
    "            used.discard(i)\n",
    "        for i_ in range(0,my_len):\n",
    "            dfs(i_,tiles,\"\")\n",
    "        # for item in chongfu:\n",
    "        #     print(item)\n",
    "        return len(chongfu)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "\n",
    "        res = set() \n",
    "        ans = -1\n",
    "        n = len(tiles)\n",
    "        # used = 0\n",
    "        # def dfs(i, path):\n",
    "        #     # [i:] \n",
    "        #     nonlocal ans, used\n",
    "        #     if path not in res:\n",
    "        #         res.add(path)\n",
    "        #         ans += 1\n",
    "            \n",
    "        #     for j in range(0, n):\n",
    "        #         if used >> j & 1 == 0:\n",
    "        #             used |= (1<<j)\n",
    "        #             dfs(j+1, path+tiles[j])\n",
    "        #             used ^= (1<<j)\n",
    "        # dfs(0, \"\")\n",
    "        # return ans\n",
    "\n",
    "        used = 0\n",
    "        def dfs(i, path, used):\n",
    "            # [i:] \n",
    "            nonlocal ans\n",
    "            if path not in res:\n",
    "                res.add(path)\n",
    "                ans += 1\n",
    "            \n",
    "            for j in range(0, n):\n",
    "                if used >> j & 1 == 0:\n",
    "                    dfs(j+1, path+tiles[j], used | (1<<j))\n",
    "        dfs(0, \"\", 0)\n",
    "        return ans\n",
    "\n",
    "        # def dfs(i, path, used):\n",
    "        #     # [i:] \n",
    "        #     nonlocal ans\n",
    "        #     if path not in res:\n",
    "        #         res.add(path)\n",
    "        #         print(path)\n",
    "        #         ans += 1\n",
    "            \n",
    "        #     for j in range(0, n):\n",
    "        #         if used >> i & 1 == 0:\n",
    "        #             dfs(j+1, path+tiles[j], used | (1<<i))\n",
    "        # dfs(0, \"\", 0)\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        self.ans = set()\n",
    "\n",
    "        def dfs(cur, temp):\n",
    "            for i, n in enumerate(temp):\n",
    "                if not n:\n",
    "                    temp[i] = True\n",
    "                    self.ans.add(cur + tiles[i])\n",
    "                    dfs(cur + tiles[i], temp)\n",
    "                    temp[i] = False\n",
    "        \n",
    "        dfs(\"\", [False] * len(tiles))\n",
    "\n",
    "        return len(self.ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        # 全排列 + 去重\n",
    "        res = set()\n",
    "        tiles = [ch for ch in tiles]\n",
    "        # i 指示当前位置\n",
    "        # path 存之前的所有路径\n",
    "        def allPath(i, path):\n",
    "            # print(i, 'path', path, tiles)\n",
    "            res.add(''.join(path))\n",
    "            \n",
    "            if i == len(tiles):\n",
    "                return\n",
    "            for j in range(i, len(tiles)):\n",
    "                tiles[i], tiles[j] = tiles[j], tiles[i]\n",
    "                allPath(i+1, path[:])\n",
    "                allPath(i+1, path[:] + [tiles[i]])\n",
    "                tiles[i], tiles[j] = tiles[j], tiles[i]\n",
    "        allPath(0, [])\n",
    "        print(res)\n",
    "        return len(res)-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        ans=set()\n",
    "        n=len(tiles)\n",
    "        vis=[0]*n\n",
    "        def dfs(i,t):\n",
    "            if i==n:\n",
    "                if t not in ans and t!=\"\":\n",
    "                    ans.add(t) \n",
    "                return \n",
    "            for j in range(n):\n",
    "                if vis[j]==0:\n",
    "                    vis[j]=1\n",
    "                    dfs(i+1,t+tiles[j])\n",
    "                    vis[j]=0\n",
    "            dfs(i+1,t)\n",
    "        \n",
    "        dfs(0,\"\")\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        ans=set()\n",
    "        n=len(tiles)\n",
    "        vis=[0]*n\n",
    "        def dfs(i,t):\n",
    "            if t not in ans and t!=\"\":\n",
    "                    ans.add(t) \n",
    "            if i==n:\n",
    "                if t not in ans and t!=\"\":\n",
    "                    ans.add(t) \n",
    "                return \n",
    "            for j in range(n):\n",
    "                if vis[j]==0:\n",
    "                    vis[j]=1\n",
    "                    dfs(i+1,t+tiles[j])\n",
    "                    vis[j]=0\n",
    "       \n",
    "        dfs(0,\"\")\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTilePossibilities(self, tiles: str) -> int:\n",
    "        ans = set()\n",
    "        n = len(tiles)\n",
    "        \n",
    "        def backtrack(s=''):\n",
    "            if s and s not in ans:\n",
    "                ans.add(s[:])\n",
    "            for i in range(n):\n",
    "                seen = set()\n",
    "                if i not in visited and tiles[i] not in seen:\n",
    "                    seen.add(tiles[i])\n",
    "                    visited.add(i)\n",
    "                    backtrack(s)\n",
    "                    backtrack(s+tiles[i])\n",
    "                    visited.remove(i)\n",
    "        \n",
    "        visited = set()\n",
    "        backtrack()\n",
    "        return len(ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
